#include <stdio.h>
#include <stdlib.h>
typedef struct ListNode
{
	int data;
	struct ListNode* next;
}ListNode;

int init_LinkList(ListNode** H)
{
	//产生一个头结点，数据域不放数据 
	(*H) = (ListNode*)malloc(sizeof(ListNode));
	if((*H) == NULL)
	{
		return 0;
	}
	(*H)->data = -1;
	(*H)->next = NULL;
	return 1;
}
int TailInsert_LinkList(ListNode* h)
{
	ListNode* p = h;
	ListNode* q = NULL;
	int t;
	while(1)
	{
		int n = 0;
		puts("输入结点值：（f结束）");
		n = scanf("%d",&t);
		if(n != 1)
		{
			break;
		}
		q = (ListNode*)malloc(sizeof(ListNode));
		if(q == NULL)
		{
			return 0;
		}
		q->data = t;
		q->next = p->next;
		p->next = q;	
		p = q;
	}
	return 1;
}
void traverse_LinkList(ListNode* h)
{
	ListNode* p = h->next;
	while(p != NULL)
	{
		printf("%d ",p->data);	
		p = p->next;
	}
}
void reverse_LinkList(ListNode* h)
{
	int num = 0;
	
	ListNode* p = h->next;
	while(p != NULL)
	{
		//printf("%d ",p->data);
		num++;	
		p = p->next;
	}
	//printf("num=%d\n",num);
	ListNode* a[num];//C99
	
	p = h->next;
	int k = 0;
	
	while(p != NULL)
	{
		a[k++] = p;
		p = p->next;
	}
	/****************关键代码*****************/
	for(int i = num - 1;i >= 0;i--)
	{
		if(i == 0)
		{
			a[i]->next = NULL;//原首元结点的next指向NULL
		}
		else
		{
			a[i]->next = a[i-1];//逆转操作
		}
	}
	h->next = a[num-1];//头结点的next指向完成逆转后的首元结点
	/****************关键代码*****************/
	return;
}
int main()
{
	ListNode* L;
	init_LinkList(&L);
	TailInsert_LinkList(L);
	traverse_LinkList(L);
	puts("\n开始逆转单链表！");
	reverse_LinkList(L);
	traverse_LinkList(L);

	return 0;
}